package string;

/**
 * Created with IntelliJ IDEA.
 * Description: 28.找出字符串中第一个匹配项的下标
 * User: Li_yizYa
 * Date: 2025—04—07
 * Time: 21:47
 */
public class Solution5 {
    public static void main(String[] args) {
        String haystack = "sadbutsad", needle = "tsad";
        System.out.println(strStr(haystack, needle));
    }
    public static int strStr(String haystack, String needle) {
        int m = needle.length();
        if (m == 0) {
            return 0;
        }
        int n = haystack.length();
        if (n < m) {
            return -1;
        }
        int i = 0;
        int j = 0;
        while (i < n - m + 1) {
            // 找到首字母相等的
            while (i < n && haystack.charAt(i) != needle.charAt(j)) {
                i++;
            }
            if (i == n) {
                return -1;
            }
            i++;
            j++;
            while (i < n && j < m && haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            }
            if (j == m) {
                return i - j;
            } else {
                i -= j - 1;
                j = 0;
            }
        }
        return -1;
    }

    public static int strStr2(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();
        char[] s1 = haystack.toCharArray();
        char[] s2 = needle.toCharArray();
        for (int i = 0; i < n - m + 1; i++) {
            int a = i;
            int b = 0;
            while (b < m && s1[a] == s2[b]) {
                a++;
                b++;
            }
            if (b == m) {
                return i;
            }
        }
        return -1;
    }
    public static int strStr1(String haystack, String needle) {
        if (needle.length() == 0 || needle == null) {
            return -1;
        }
        int[] next = new int[needle.length()];
        getNext(next, needle);
        int j = -1;
        for (int i = 0; i < haystack.length(); i++) {
            while (j >= 0 && haystack.charAt(i) != needle.charAt(j + 1)) {
                j = next[j];
            }
            if (haystack.charAt(i) == needle.charAt(j + 1)) {
                j++;
            }
            if (j == needle.length() - 1) {
                return (i - needle.length() + 1);
            }
        }
        return -1;
    }
    private static void getNext(int[] next, String s) {
        int j = -1;
        next[0] = j;
        for (int i = 1; i < s.length(); i++) {
            while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) {
                j = next[j];
            }
            if (s.charAt(i) == s.charAt(j + 1)) {
                j++;
            }
            next[i] = j;
        }
    }
}
